#include "cfg.h"

void print_expressions(expression * expr_list, char * proc_name, int num_exprs) {
	expression * current_expr = NULL;
	
	printf("expressions %s %d\n", proc_name, num_exprs);
	for(current_expr = expr_list; current_expr; current_expr = current_expr->next) {
		printf("expr %d %d\n", current_expr->number, current_expr->instr->number);
	}

	printf("\n");
}

expression * find_node(expression * expr_list, simple_instr * instr) {
	expression * current_expr = expr_list;

	for( ; current_expr; current_expr = current_expr->next) {
		if(current_expr->instr->instr->opcode == instr->opcode && current_expr->r1 == instr->u.base.src1 && current_expr->r2 == instr->u.base.src2)
			return current_expr;
	}

	return NULL;
}

int find_expressions(instr_node * instr_head, expression ** expr_list) {
	instr_node * current = instr_head;
	simple_instr * instr = NULL;
	expression * last_expr = NULL;
	int expr_number = 0;

	while(current) {
		instr = current->instr;

		// check if the instruction is of base form.
		if(simple_op_format(instr->opcode) == BASE_FORM) {
			// check if both src regs are PSEDUO REGS
			simple_reg * r1 = instr->u.base.src1;
			simple_reg * r2 = instr->u.base.src2;

			if(instr->opcode == NOT_OP || instr->opcode == CVT_OP) {
				if(r1->kind == PSEUDO_REG && find_node(*expr_list, instr) == NULL) {
					expression * newexpr = (expression *) malloc(sizeof(expression));
					newexpr->number = ++expr_number;
					newexpr->instr = current;
					newexpr->r1 = r1;
					newexpr->r2 = r2;
					newexpr->prev = last_expr;
					newexpr->next = NULL;

					if(*expr_list == NULL)
						*expr_list = newexpr;
					else
						last_expr->next = newexpr;
					last_expr = newexpr;
				}
			} 
			else if(r1 && r1->kind == PSEUDO_REG && r2 && r2->kind == PSEUDO_REG) {
				if(find_node(*expr_list, instr) == NULL) {
					expression * newexpr = (expression *) malloc(sizeof(expression));
					newexpr->number = ++expr_number;
					newexpr->instr = current;
					newexpr->r1 = r1;
					newexpr->r2 = r2;
					newexpr->dest = current->next->instr->u.base.dst;
					newexpr->prev = last_expr;
					newexpr->next = NULL;

					if(*expr_list == NULL) {
						*expr_list = newexpr;
					} else {
						last_expr->next = newexpr;
					}
					last_expr = newexpr;
				}
			}				
		}

		current = current->next;
	}
	return expr_number;
}

void find_kills(simple_instr * instr, basic_block_node * current_block, expression * expr_list) {
	simple_reg * dst = NULL;
	switch(simple_op_format(instr->opcode)) {
		case BASE_FORM: {
			dst = instr->u.base.dst; 
			break;
		}
		case LDC_FORM: {
			dst = instr->u.ldc.dst;
			break;
		}
		case CALL_FORM: {
			dst = instr->u.call.dst;
			break;
		}
	}
	
	if(dst) {
		expression * current_expr = expr_list;

		while (current_expr) {
			if(current_expr->r1 == dst || current_expr->r2 == dst) {
				set_bit(current_block->eval_expr, current_expr->number - 1, FALSE);
				set_bit(current_block->kill_expr, current_expr->number - 1, TRUE);
			}
			current_expr = current_expr->next;
		}	
	}
}

// finds the eval and kill sets
void expr_init(basic_block_node * block_head, int size, expression * expr_list) {
	block_ptr * stack = NULL;
	basic_block_node * current_block = NULL;

	for(current_block = block_head; current_block; current_block = current_block->next) {
		instr_node * current_instr = NULL;
		current_block->eval_expr = new_bit_vector(size);
		current_block->kill_expr = new_bit_vector(size);
		current_block->aein = new_bit_vector(size);
		current_block->aeout = new_bit_vector(size);

		for(current_instr = current_block->start; current_instr && current_instr != current_block->end->next; current_instr = current_instr->next) {
			expression * current_expr = find_node(expr_list, current_instr->instr);
			if(current_expr != NULL) {
				set_bit(current_block->eval_expr, current_expr->number - 1, TRUE);
			}
			find_kills(current_instr->instr, current_block, expr_list);
		}
		set_all_bits(current_block->aeout, TRUE);
	}	

	while(dfa_start(block_head, ae_meet, ae_transferfunc, &stack, 0)) {
		stack = NULL;
	}
}

void print_eval_expr(basic_block_node * block_head, char * proc_name, int expr_count) {
	basic_block_node * current_block;
	int i =0;
	printf("eval_ae_sets %s %d\n", proc_name, expr_count);

	for(current_block = block_head; current_block; current_block = current_block->next) {
		printf("eval_ae %d ", current_block->number);
		for(i = 0; i < current_block->eval_expr->num_bits; i++)
			printf("%d", get_bit(current_block->eval_expr, i));
		printf("\n");
	}
	printf("\n");
}


void print_kill_expr(basic_block_node * block_head, char * proc_name, int expr_count) {
	basic_block_node * current_block;
	int i = 0;
	printf("kill_ae_sets %s %d\n", proc_name, expr_count);

	for(current_block = block_head; current_block; current_block = current_block->next) {
		printf("kill_ae %d ", current_block->number);
		for(i = 0; i < current_block->kill_expr->num_bits; i++)
			printf("%d", get_bit(current_block->kill_expr, i));
		printf("\n");
	}
	printf("\n");
}

// meet operator to calculate aein
int ae_meet(basic_block_node * block) {
	block_ptr * predecessor = block->predecessor;	
	
	if(predecessor)
		set_all_bits(block->aein, TRUE);
	else set_all_bits(block->aein, FALSE);
	
	while(predecessor) {
		and_bits(block->aein, predecessor->block->aeout);
		predecessor = predecessor->next;
	}

	return FALSE;
}

// meet operator to calculate aeout
int ae_transferfunc(basic_block_node * block) {
	bit_vector * oldout = new_bit_vector(block->aeout->num_bits);

	copy_bits(oldout, block->aeout);

	copy_bits(block->aeout, block->aein);
	subtract_bits(block->aeout, block->kill_expr);
	or_bits(block->aeout, block->eval_expr);

	return !bits_are_equal(oldout, block->aeout);
}
	
void print_aeout(basic_block_node * block_head, char * proc_name, int blockCount) {
	basic_block_node * current_block = block_head;
	int i;

	printf("available_exprs %s %d\n", proc_name, blockCount);
	while(current_block) {
		printf("avail_exprs_out %d ", current_block->number);
		for(i = 0; i < current_block->aeout->num_bits; i++)
			printf("%d", get_bit(current_block->aeout, i));
		printf("\n");
		current_block = current_block->next;
	}
}

